<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>滑动窗口算法 | 悄悄的卷，然后卷死所有人</title>
    <meta name="description" content="这是一个奇怪的地方">
    <link rel="stylesheet" href="/blobview/assets/style.019f39fc.css">
    <link rel="modulepreload" href="/blobview/assets/Home.d05cdc04.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <link rel="modulepreload" href="/blobview/assets/fe_suanfa_滑动窗口.md.08f684ff.lean.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <meta name="twitter:title" content="滑动窗口算法 | 悄悄的卷，然后卷死所有人">
    <meta property="og:title" content="滑动窗口算法 | 悄悄的卷，然后卷死所有人">
  </head>
  <body>
    <div id="app"><!--[--><div class="theme"><header class="nav-bar" data-v-675d8756><div class="sidebar-button" data-v-675d8756><svg class="icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z" class></path></svg></div><a class="nav-bar-title" href="/blobview/" aria-label="悄悄的卷，然后卷死所有人, back to home" data-v-675d8756 data-v-4a583abe><!----> 悄悄的卷，然后卷死所有人</a><div class="flex-grow" data-v-675d8756></div><div class="nav" data-v-675d8756><nav class="nav-links" data-v-675d8756 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav></div><!--[--><!--]--></header><aside class="sidebar" data-v-83e92a68><nav class="nav-links nav" data-v-83e92a68 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav><!--[--><!--]--><ul class="sidebar-links" data-v-83e92a68><!--[--><li class="sidebar-link"><a class="sidebar-link-item" href="#简介">简介</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#算法实现">算法实现</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#简单demo">简单demo</a><!----></li><!--]--></ul><!--[--><!--]--></aside><div class="sidebar-mask"></div><main class="page" data-v-7eddb2c4><div class="container" data-v-7eddb2c4><!--[--><!--]--><div style="position:relative;" class="content" data-v-7eddb2c4><div><h1 id="滑动窗口算法" tabindex="-1">滑动窗口算法 <a class="header-anchor" href="#滑动窗口算法" aria-hidden="true">#</a></h1><h2 id="简介" tabindex="-1">简介 <a class="header-anchor" href="#简介" aria-hidden="true">#</a></h2><p>滑动窗口算法是一种用于解决数组或字符串的子问题的算法。它通过维护一个窗口，并在窗口内滑动来解决问题。具体步骤如下：</p><ol><li>定义左右指针，初始化为数组或字符串的起始位置。</li><li>将右指针向右移动，扩大窗口，直到窗口内包含了所需的元素或字符数量。</li><li>计算当前答案，并将左指针向右移动，缩小窗口，直到窗口内不再包含多余的元素或字符。</li><li>重复步骤 2 和步骤 3，直到右指针到达数组或字符串的末尾。</li><li>滑动窗口算法的优势在于它的时间复杂度为 O(N)，其中 N 为数组或字符串长度。它适用于解决有限大小子串/子数组问题的问题，如最小子串问题，最长无重复字符子串问题等。</li></ol><h2 id="算法实现" tabindex="-1">算法实现 <a class="header-anchor" href="#算法实现" aria-hidden="true">#</a></h2><div class="language-js"><pre><code><span class="token comment">/**
 * 该函数用于寻找一个连续子数组，使得子数组元素之和大于等于target，返回最短子数组长度
 * @param {number[]} nums - 给定的整数数组
 * @param {number} target - 目标和
 * @return {number} 返回最短可行子数组长度，如果不存在则返回0
 **/</span>
<span class="token keyword">function</span> <span class="token function">slidingWindow</span><span class="token punctuation">(</span><span class="token parameter">nums<span class="token punctuation">,</span> target</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 用左右指针定义一个滑动窗口，初始状态right在left的左侧</span>
  <span class="token keyword">let</span> left <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// left指针指向当前窗口的最左端</span>
  <span class="token keyword">let</span> right <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// right指针指向当前窗口的最右端</span>
  <span class="token keyword">let</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// sum用于累加当前窗口内的元素之和</span>
  <span class="token keyword">let</span> minLength <span class="token operator">=</span> <span class="token number">Infinity</span><span class="token punctuation">;</span> <span class="token comment">// 用于记录最小长度，初始设为正无穷大（无解）</span>

  <span class="token keyword">while</span> <span class="token punctuation">(</span>right <span class="token operator">&lt;</span> nums<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 当right指针移到数组末尾，终止循环</span>
    sum <span class="token operator">+=</span> nums<span class="token punctuation">[</span>right<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 向窗口内加入一个元素</span>
    right<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 移动右指针</span>

    <span class="token keyword">while</span> <span class="token punctuation">(</span>sum <span class="token operator">&gt;=</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 如果窗口内的元素之和大于等于目标和，进行缩小窗口的操作</span>
      <span class="token comment">// 记录最短子数组长度</span>
      minLength <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>minLength<span class="token punctuation">,</span> right <span class="token operator">-</span> left<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token comment">// 从窗口左侧移除一个元素</span>
      sum <span class="token operator">-=</span> nums<span class="token punctuation">[</span>left<span class="token punctuation">]</span><span class="token punctuation">;</span>
      left<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 移动左指针</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 找到最短子数组长度，如果不存在长度为0</span>
  <span class="token keyword">return</span> minLength <span class="token operator">===</span> <span class="token number">Infinity</span> <span class="token operator">?</span> <span class="token number">0</span> <span class="token operator">:</span> minLength<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 测试函数</span>
<span class="token keyword">let</span> nums <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">let</span> target <span class="token operator">=</span> <span class="token number">7</span><span class="token punctuation">;</span>
<span class="token keyword">let</span> length <span class="token operator">=</span> <span class="token function">slidingWindow</span><span class="token punctuation">(</span>nums<span class="token punctuation">,</span> target<span class="token punctuation">)</span><span class="token punctuation">;</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>length<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 输出2（符合条件的最短子数组为[4,3]，长度为2）</span>
</code></pre></div><h2 id="简单demo" tabindex="-1">简单demo <a class="header-anchor" href="#简单demo" aria-hidden="true">#</a></h2><p>滑动窗口（Sliding Window）算法是一种使用指针移动来解决数组/字符串的子区间问题的算法。它可用于解决一些数组/字符串的子区间问题，如最长子串、最小子数组等。 以下是滑动窗口的最简单的模板代码：</p><div class="language-js"><pre><code><span class="token keyword">function</span> <span class="token function">slidingWindow</span><span class="token punctuation">(</span><span class="token parameter">s</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> n <span class="token operator">=</span> s<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
  <span class="token keyword">let</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 移动j指针右侧，扩展窗口</span>
    <span class="token comment">// ...</span>

    <span class="token comment">// 移动i指针左侧，缩小窗口</span>
    <span class="token comment">// ...</span>

    <span class="token comment">// 更新结果</span>
    ans <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> j <span class="token operator">-</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

</code></pre></div><p>在这个模板中，我们使用两个指针i和j来表示滑动窗口的左右边界。它们在移动时可以向左或向右移动，从而扩展或缩小窗口的大小。在算法的每个时间步骤中，我们都能够得到当前窗口的范围，并使用它来更新答案值。 需要注意的是，具体的扩展和缩小窗口的策略会根据题目而定，例如可以根据窗口内的元素进行判断，或者根据题目要求进行调整。具体实现时，可以在// 移动j指针右侧,扩展窗口和// 移动i指针左侧，缩小窗口的地方进行相应的处理。 例如下面一个示例问题：给定一个字符串s，找到最长的子字符串，使得其中的字符仅出现一次。</p><div class="language-js"><pre><code><span class="token keyword">function</span> <span class="token function">longestSubstring</span><span class="token punctuation">(</span><span class="token parameter">s</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> n <span class="token operator">=</span> s<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
  <span class="token keyword">let</span> set <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Set</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">let</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">has</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 窗口中出现重复元素时，缩小窗口</span>
      set<span class="token punctuation">.</span><span class="token function">delete</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      i<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 扩展窗口</span>
    ans <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> j <span class="token operator">-</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 更新答案</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>在上面的示例中，我们使用Set数据结构来记录窗口内出现的字符。一旦发现窗口中出现重复的字符，就不断缩小窗口，直到窗口中不再存在重复字符。在这个例子中，我们可以发现，每当遇到重复字符时，当前窗口的开头位置为i，当前窗口的结尾位置为j，当前窗口的大小为j-i+1。我们可以用这个大小来不断更新答案。</p></div></div><footer class="page-footer" data-v-7eddb2c4 data-v-fb8d84c6><div class="edit" data-v-fb8d84c6><div class="edit-link" data-v-fb8d84c6 data-v-1ed99556><!----></div></div><div class="updated" data-v-fb8d84c6><!----></div></footer><!----><!--[--><!--]--></div></main></div><!----><!--]--></div>
    <script>__VP_HASH_MAP__ = JSON.parse("{\"fe_algorithm.md\":\"e1054222\",\"fe_errormd_chrome插件开发指南.md\":\"8310a77a\",\"fe_errormd_mysql密码遗忘.md\":\"37b8860e\",\"fe_secondary_javascript_descriptors.md\":\"cd9a7474\",\"fe_secondary_javascript_javascript.md\":\"42853649\",\"fe_secondary_javascript_jicheng.md\":\"1cd0c4dc\",\"fe_secondary_javascript_jscopy.md\":\"66795111\",\"fe_secondary_javascript_js数据类型.md\":\"c6bc851f\",\"fe_secondary_javascript_let const var 的区别.md\":\"685e3545\",\"fe_secondary_javascript_weakmap.md\":\"2a0ba820\",\"fe_secondary_javascript_作用域.md\":\"220cfcf9\",\"fe_secondary_javascript_变量提升.md\":\"b63f20ee\",\"fe_secondary_javascript_闭包.md\":\"5404cbcf\",\"fe_secondary_python_基础知识.md\":\"ae39dc27\",\"fe_secondary_vite_vite杂烩记录.md\":\"aa7cf9a4\",\"fe_secondary_webpack_loader与plugin的不同.md\":\"e2712a7c\",\"fe_secondary_interviews_jstype.md\":\"b3e700ba\",\"fe_secondary_interviews_mianshi.md\":\"218f21c3\",\"fe_secondary_interviews_modular.md\":\"38434f4f\",\"fe_secondary_interviews_network.md\":\"d5842ea6\",\"fe_suanfa_tree树结构.md\":\"d41c852f\",\"fe_suanfa_二分查找.md\":\"28f745d1\",\"fe_suanfa_二叉树.md\":\"836f7969\",\"fe_suanfa_二叉树后序遍历.md\":\"af43c381\",\"fe_suanfa_二叉树展开链表.md\":\"cc410293\",\"fe_suanfa_二叉树最小深度.md\":\"d272316f\",\"fe_suanfa_二叉树的所有路径.md\":\"70f2feac\",\"fe_suanfa_二叉树的最大深度.md\":\"ab1fe25c\",\"fe_suanfa_冒泡排序.md\":\"b91ecca4\",\"fe_suanfa_前中后序遍历.md\":\"997426ab\",\"fe_suanfa_前缀和.md\":\"6ec90ae8\",\"fe_suanfa_区域和检索数组不可变.md\":\"6e447cdb\",\"fe_suanfa_反转数组.md\":\"c28c7d5f\",\"fe_suanfa_将有序数组转换为二叉搜索树.md\":\"6a79c21d\",\"fe_suanfa_差分.md\":\"101d6b54\",\"fe_suanfa_快速排序.md\":\"575fe1af\",\"fe_suanfa_插入排序.md\":\"078511c5\",\"fe_suanfa_滑动窗口.md\":\"08f684ff\",\"fe_suanfa_翻转二叉树.md\":\"1a866015\",\"fe_suanfa_选择排序.md\":\"a25eac11\",\"fe_suanfa_链表反转.md\":\"a642cc7a\",\"fe_web3_ethers_01-hellovitalik.md\":\"162c31f8\",\"fe_web3_ethers_02-合约交互.md\":\"08f30902\",\"fe_web3_ethers_03-发送eth.md\":\"fbf8825d\",\"index.md\":\"64947f2b\"}")</script>
    <script type="module" async src="/blobview/assets/app.a4363fd4.js"></script>
    
  </body>
</html>